home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / graph_alg / _embedding.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  6.1 KB  |  257 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _embedding.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. /*******************************************************************************
  18. *                                                                              *
  19. *  EMBEDDING   (straight line embedding)                                       *
  20. *                                                                              *
  21. *  K. Mehlhorn (1989)                                                          *
  22. *                                                                              *
  23. *******************************************************************************/
  24.  
  25. #include <LEDA/graph_alg.h>
  26.  
  27.  
  28. const int A = -2; 
  29. const int B = -1; 
  30.  
  31. static node_array<list_item>  Classloc;
  32. static node_array<int>  ord, labelled, Class;
  33. static node_array<node> first, second, last;
  34. static edge_array<edge> reversal;
  35.  
  36. void label_node(graph& G, list<node>& L, int& count,
  37.                 list<node>& Al,list<node>& Bl,list<node>*& Il,
  38.                 node v, node c)
  39.  
  40. { // labels the node v; c is the special node which is to be labelled
  41.   // last; the details are described in lemma 10
  42.   edge e;
  43.   L.append(v);
  44.   ord[v]=count++; 
  45.   labelled[v]=1;
  46.  
  47.   forall_adj_edges(e,v)
  48.   { edge e1 = reversal[e];
  49.     node tt = target(e);
  50.     int i;
  51.  
  52.     if (labelled[tt] && !labelled[target(G.cyclic_adj_succ(e))])
  53.       { first[v]=tt; 
  54.         second[v]=target(G.cyclic_adj_pred(e));
  55.        }
  56.  
  57.     if (labelled[tt] && !labelled[target(G.cyclic_adj_pred(e))]) last[v]=tt;
  58.  
  59.     if (!labelled[tt] && (tt != c))
  60.       { if (Class[tt] == A) 
  61.           { Al.del(Classloc[tt]); 
  62.             Classloc[tt] = Bl.push(tt);
  63.             Class[tt]=B;
  64.            }  
  65.         else 
  66.           { if (Class[tt] == B) 
  67.                { Bl.del(Classloc[tt]);
  68.                  i = 2-labelled[target(G.cyclic_adj_succ(e1))]
  69.                       -labelled[target(G.cyclic_adj_pred(e1))];
  70.                 }
  71.             else 
  72.                { i=Class[tt];
  73.                  Il[i].del(Classloc[tt]);
  74.                  i = i+1-labelled[target(G.cyclic_adj_succ(e1))]
  75.                         -labelled[target(G.cyclic_adj_pred(e1))];
  76.                 }
  77.  
  78.              Class[tt]=i;
  79.              Classloc[tt]=Il[i].push(tt);
  80.  
  81.            }//end else case
  82.  
  83.       }//end if
  84.  
  85.   }//end 
  86.  
  87. }//end of label_node
  88.  
  89.  
  90. void compute_labelling(graph& G,list<node>& L, list<node>& Pi)
  91. { /* computes the ordering of lemma 10 in List L ,the sequence pi
  92.      in List Pi, the function L^-1(v) in Array ord, and the functions
  93.      first,second,last of lemma 11 in the corresponding Arrays
  94.    */
  95.   node v,a,b,c;
  96.  
  97.   /* zuerst berechne ich die drei Knoten,die am Rand des aeusseren 
  98.      Gebiets liegen sollen
  99.    */
  100.  
  101.   a=G.first_node();
  102.   list<edge> temp = G.adj_edges(a);
  103.   b = target(temp.pop());
  104.   c = target(temp.pop());
  105.  
  106.  
  107. /*
  108.   node_array<int> labelled(G,0);
  109. */
  110.  
  111.   labelled.init(G,0);
  112.  
  113.   int count = 0;
  114.   
  115.   list<node> Al ;
  116.  
  117. /*
  118.   node_array<int> Class(G); 
  119.   node_array<list_item> Classloc(G);
  120. */
  121.  
  122.   Class.init(G); 
  123.   Classloc.init(G);
  124.  
  125.   forall_nodes(v,G) { Classloc[v] = Al.push(v);Class[v]=A;}
  126.  
  127.   list<node> Bl;
  128.   list<node>* Il = new list<node>[G.number_of_nodes()];
  129.   
  130.   label_node(G,L,count,Al,Bl,Il,a,c);
  131.   label_node(G,L,count,Al,Bl,Il,b,c);
  132.  
  133.   while (v=Il[1].pop()) label_node(G,L,count,Al,Bl,Il,v,c);
  134.  
  135.   label_node(G,L,count,Al,Bl,Il,c,c);
  136.  
  137.    //nun berechne ich noch first second und last des Knoten c 
  138.   first[c]=a;
  139.   last[c]=b;
  140.  
  141.   edge e;
  142.   forall_adj_edges(e,c) if (target(e)==a) second[c]=target(G.cyclic_adj_pred(e));
  143.   
  144.  //nun die Folge Pi
  145.   node_array<list_item> Piloc(G);
  146.   Piloc[a] = Pi.push(a);
  147.   Piloc[b] = Pi.append(b);
  148.   forall(v,L) if (v != a && v != b) Piloc[v] = Pi.insert(v,Piloc[second[v]],-1);
  149.  
  150. }//end of compute_labelling 
  151.  
  152. void move_to_the_right(list<node>& Pi, node v, node w, 
  153.                        node_array<int>& ord, node_array<int>& x)
  154.  
  155. { //increases the x-coordinate of all nodes which follow w in List Pi
  156.   //and precede v in List L,i.e., have a smaller ord value than v
  157.   int seen_w = 0;
  158.   node z;
  159.   forall(z,Pi)
  160.   { if (z==w) seen_w=1;
  161.     if (seen_w && (ord[z]<ord[v])) x[z]=x[z]+1;
  162.   }
  163. }
  164.  
  165.  
  166. int STRAIGHT_LINE_EMBEDDING(graph& G,node_array<int>& x, node_array<int>& y)
  167. {
  168.  // computes a straight-line embedding of the planar map G into
  169.  // the 2n by n grid. The coordinates of the nodes are returned
  170.  // in the Arrays x and y. Returns the maximal coordinate.
  171.  
  172. list<node> L;
  173. list<node> Pi;
  174. list<edge> TL;
  175.  
  176. node v;
  177. edge e;
  178. int maxcoord=0;
  179.  
  180. /*
  181. node_array<int>  ord(G);
  182. node_array<node> first(G), second(G), last(G);
  183. */
  184.  
  185. ord.init(G);
  186. first.init(G);
  187. second.init(G);
  188. last.init(G);
  189.  
  190.  
  191. TL = TRIANGULATE_PLANAR_MAP(G);
  192.  
  193. /*
  194. edge_array<edge> reversal(G);
  195. */
  196.  
  197. reversal.init(G);
  198. compute_correspondence(G,reversal);
  199.  
  200. compute_labelling(G,L,Pi);
  201.  
  202.  
  203. //I now embed the first three nodes
  204.  
  205. v = L.pop();
  206. x[v]=y[v]=0;
  207.  
  208. v=L.pop();
  209. x[v]=2;y[v]=0;
  210.  
  211. v=L.pop();
  212. x[v]=y[v]=1;
  213.  
  214. //I now embed the remaining nodes
  215.  
  216. while (v=L.pop())
  217.  { // I first move the nodes depending on second[v] by one unit
  218.    // and the the nodes depending on last[v] by another unit to the 
  219.    // right
  220.  
  221.    move_to_the_right(Pi,v,second[v],ord,x);
  222.    move_to_the_right(Pi,v,last[v],ord,x);
  223.  
  224.    // I now embed v at the intersection of the line with slope +1
  225.    // through first[v] and the line with slope -1 through last[v]
  226.  
  227.    int x_first_v = x[first[v]];
  228.    int x_last_v =  x[last[v]];
  229.    int y_first_v = y[first[v]];
  230.    int y_last_v =  y[last[v]];
  231.  
  232.    x[v]=(y_last_v - y_first_v + x_first_v + x_last_v)/2;
  233.    y[v]=(x_last_v - x_first_v + y_first_v + y_last_v)/2;
  234.  }
  235.  
  236. // delete triangulation edges
  237.  
  238. forall(e,TL) G.del_edge(e);
  239.  
  240. forall_nodes(v,G) maxcoord = Max(maxcoord,Max(x[v],y[v]));
  241. return maxcoord;
  242.  
  243. }
  244.  
  245.  
  246.  
  247. int STRAIGHT_LINE_EMBEDDING(graph& G,node_array<double>& x, node_array<double>& y)
  248. { node v;
  249.   node_array<int> x0(G), y0(G);
  250.  
  251.   int result = STRAIGHT_LINE_EMBEDDING(G,x0,y0);
  252.  
  253.   forall_nodes(v,G) { x[v] = x0[v];
  254.                       y[v] = y0[v]; }
  255.   return result;
  256. }
  257.